import java.util.*;

public class project {
    public List<Integer> sequentialDigits(int low, int high) {
        List<Integer> list=new ArrayList<>();
        for(int i=1;i<10;i++){
            int sum=i;
            for(int j=i+1;j<10;j++){
                sum=sum*10+j;
                if(sum>=low&&sum<=high){
                    list.add(sum);
                }else if(sum>=high){
                    break;
                }
            }
        }
        Collections.sort(list);
        return list;
    }















    public int minDeletions(String s) {
        Map<Character,Integer> map=new HashMap<>();
        int maxLen=0;
        for(char ch:s.toCharArray()){
            map.put(ch,map.getOrDefault(ch,0)+1);
            maxLen=Math.max(maxLen,map.get(ch));
        }
        boolean[] booleans=new boolean[maxLen];
        int ret=0;
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            if(!booleans[entry.getValue()-1]){
                booleans[entry.getValue()-1]=true;
            }else{
                for(int i=entry.getValue()-1;i>=0;){
                    if(!booleans[i]){
                        ret+=entry.getValue()-i-1;
                    }
                    i--;
                    if(i==-1){
                        ret+=entry.getValue();
                    }
                }
            }
        }
        return ret;
    }













    public int minimumDeletions(String s) {
        int len=s.length();
        int ret=0;
        int index=0;
        while (index<len&&s.charAt(index)=='a'){
            index++;
        }
        int countA=0;
        int countB=0;
        while (index<len){
            char ch=s.charAt(index);
            if(ch=='a'){
                countA++;
            }else{
                countB++;
            }
            if(countA>=countB){
                ret+=countB;
                countA=0;
                countB=0;
            }
            index++;
        }
        ret+=countA;
        return ret;
    }






















    public int lenLongestFibSubseq(int[] arr) {
        int len=arr.length;
        Set<Integer> set=new HashSet<>();
        for(int value:arr){
            set.add(value);
        }
        int maxLen=0;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                int x=arr[j];
                int sum=arr[i]+arr[j];
                int size=2;
                while (set.contains(sum)){
                    int y=sum;
                    sum+=x;
                    x=y;
                    size++;
                    maxLen=Math.max(maxLen,size);
                }
            }
        }
        return maxLen>2?maxLen:0;
    }















    public int countPrimeSetBits(int left, int right) {
        int ret=0;
        for(int i=left;i<=right;i++){
            if(find(Integer.bitCount(i))){
                ret++;
            }
        }
        return  ret;
    }
    public boolean find(int value){
        if(value<2){
            return false;
        }
        for(int i=2;i*i<=value;i++){
            if(value%i==0){
                return false;
            }
        }
        return true;
    }
}
